public class Parser {
	private int ptr;
	private String in;

	private void match(char c) throws Exception {
		if (in.charAt(ptr) == c) {
			ptr++;
		} else {
			throw new Exception("Invalid character at " + ptr + ": " + c);
		}
	}

	private boolean validAtomChar(char c) {
		return c != ' ' && c != '\n' && c != '\t' && c != '(' && c != ')'
				&& c != '#' && c != '[' && c != ']';
	}

	private boolean endOfString() {
		return ptr == in.length();
	}

	private void eatWhitespace() throws Exception {
		char c = cur();
		while (c == ' ' || c == '\n' || c == '\t') {
			match(c);
			c = cur();
		}
	}

	private char cur() {
		return in.charAt(ptr);
	}

	private boolean isNumber(String s) {
		return s.matches("(-|\\+)?[0-9]+(\\.[0-9]+)?");
	}

	private List<Object> parseList() throws Exception {
		// create data structure
		LinkedList<Object> lst = new LinkedList<Object>();
		match('(');
		eatWhitespace();
		while (cur() != ')') {
			// loop until finding an end paren
			if (cur() == '(') {
				// nested list
				lst.add(parseList());
			} else {
				// atom
				lst.add(parseAtom());
			}
			eatWhitespace();
		}
		match(')');
		return lst;
	}

	private Object parseAtom() throws Exception {
		String buf = "";
		while (!endOfString() && validAtomChar(cur())) {
			// build buffer
			buf += cur();
			match(cur());
		}
		// determine what's in the buffer
		if (isNumber(buf)) {
			return new BigDecimal(buf);
		} else {
			return Symbol.getSymbol(buf);
		}
	}

	public List<Object> startParser(String s) throws Exception {
		ptr = 0;
		in = s;
		LinkedList<Object> lst = new LinkedList<Object>();
		while (ptr < in.length()) {
			if (cur() == '(') {
				lst.add(parseList());
			} else {
				lst.add(parseAtom());
			}
			if (ptr != in.length()) {
				eatWhitespace();
			}
		}
		return lst;
	}

}

public class Symbol {
	private static HashMap<String, Symbol> symbolTable = new HashMap<String, Symbol>();
	private static int numSymbols;
	private String value;
	private int id;

	private Symbol(String value) {
		this.value = value;
		id = numSymbols++;
	}

	public static Symbol getSymbol(String key) {
		String value = key.toUpperCase();
		Symbol s;
		if (symbolTable.containsKey(value)) {
			s = symbolTable.get(value);
		} else {
			s = new Symbol(value);
			symbolTable.put(value, s);
		}
		return s;
	}

	public String getValue() {
		return value;
	}

	public int getId() {
		return id;
	}

	public boolean equals(Symbol s) {
		return id == s.id;
	}

	public String toString() {
		return value;
	}
}

public class Lambda {
	private Environment env;
	private Object code;
	private List<Symbol> params;

	public Lambda(Environment env, Object code, List<Symbol> params) {
		this.env = env;
		this.code = code;
		this.params = params;
	}

	public Environment getEnv() {
		return env;
	}

	public Object getCode() {
		return code;
	}

	public List<Symbol> getParams() {
		return params;
	}

	public String toString() {
		return "\\" + params + " -> " + code;
	}

}

public class Environment {
	private Environment parent;
	private HashMap<Symbol, Object> env;

	public Environment(Environment parent) {
		this.parent = parent;
		env = new HashMap<Symbol, Object>();
	}

	public Environment() {
		parent = null;
		env = new HashMap<Symbol, Object>();
	}

	public void add(Symbol s, Object o) {
		env.put(s, o);
	}

	public Object get(Symbol s) throws Exception {
		if (env.containsKey(s)) {
			return env.get(s);
		} else {
			if (parent != null) {
				return parent.get(s);
			} else {
				throw new Exception("Symbol binding not found.");
			}
		}
	}

	public void set(Symbol s, Object o) {
		if (env.containsKey(s)) {
			env.put(s, o);
		} else {
			if (parent != null) {
				parent.set(s, o);
			} else {
				env.put(s, o);
			}
		}
	}

	public String toString() {
		String str = env.toString();
		if (parent != null) {
			str += "\n" + parent;
		}
		return str;
	}

}

private static Object ifForm(List<?> lst, Environment e) throws Exception {
	Object condition = lst.get(1);
	condition = eval(condition, e);
	if (!(condition instanceof Boolean)) {
		throw new Exception("Condition did not return Boolean: "
				+ condition);
	} else {
		if ((Boolean) condition) {
			return lst.get(2);
		} else {
			return lst.get(3);
		}
	}
}

private static Object beginForm(List<?> lst, Environment e)
		throws Exception {
	if (lst.size() <= 1) {
		throw new Exception("Begin must have arguments");
	} else if (lst.size() == 2) {
		return lst.get(1);
	} else {
		eval(lst.get(1), e);
		LinkedList<Object> code = new LinkedList<Object>();
		code.add(Symbol.getSymbol("begin"));
		for (int i = 2; i < lst.size(); i++) {
			code.add(lst.get(i));
		}
		return code;
	}
}

private static Object lambdaForm(List<?> lst, Environment e) throws Exception {
	LinkedList<Object> code = new LinkedList<Object>();
	code.add(Symbol.getSymbol("begin"));
	for (int i = 2; i < lst.size(); i++) {
		code.add(lst.get(i));
	}
	List<Symbol> params = new LinkedList<Symbol>();
	Object codeArgs = lst.get(1);
	if (!(codeArgs instanceof List<?>)) {
		throw new Exception(
				"Parameters for lambda must be a list of Symbols.");
	}

	lst = (List<?>) codeArgs;
	for (int i = 0; i < lst.size(); i++) {
		if (lst.get(i) instanceof Symbol) {
			params.add((Symbol) lst.get(i));
		} else {
			throw new Exception("Expected Symbol, got " + lst.get(i));
		}
	}
	return new Lambda(e, code, params);
}

private static void defineForm(List<?> lst, Environment e) throws Exception {
	Symbol name;

	if (lst.get(1) instanceof List<?>) {

		List<?> signature = (List<?>) lst.get(1);

		name = (Symbol) signature.get(0);

		LinkedList<Symbol> params = new LinkedList<Symbol>();
		if (signature.size() > 1) {
			for (int i = 1; i < signature.size(); i++) {
				params.add((Symbol) signature.get(i));
			}
		}

		LinkedList<Object> code = new LinkedList<Object>();
		code.add(Symbol.getSymbol("begin"));
		for (int i = 2; i < lst.size(); i++) {
			code.add(lst.get(i));
		}

		Lambda expr = new Lambda(e, code, params);

		e.add(name, expr);

	} else if (lst.get(1) instanceof Symbol) {

		name = (Symbol) lst.get(1);
		Object value = eval(lst.get(2), e);

		e.add(name, value);

	} else {

		throw new Exception(
				"Define expects symbol or list as first argument.");

	}
}

public static Object eval(Object o, Environment e)
					throws Exception {
	while (true) {

		if (o instanceof Number || o instanceof Boolean) {

			// numbers, booleans, and strings are
			// self-evaluating

			return o;

		} else if (o instanceof Symbol) {

			// symbols need to be looked up in
			// the environment

			return e.get((Symbol) o);

		} else if (o instanceof List<?>) {

			// we cast o to List<?> because the parameter
			// type is lost at runtime. all we can
			// verify is that it's a list, which is all
			// that we care about anyway
			List<?> lst = (List<?>) o;

			// the input is a list, so we need to check
			// for the special cases and potentially
		 	// treat the list as a function call
			Object root = lst.get(0);

			if (root instanceof Symbol) {
				// if the first element of the list
				// (the "car") is a Symbol, we
				// need to check for the special cases
				Symbol car = (Symbol) root;

				if (car.equals
					(Symbol.getSymbol("if"))) {

					// throw error if wrong number
					// of args
					if (lst.size() != 4) {
						throw new Exception
						  ("If expects three args.");
					}

					// *change* the code and
					// *don't* return
					o = ifForm(lst, e);
					continue; // jump to top of loop!

				} else if
				  (car.equals
					(Symbol.getSymbol("lambda"))) {

					// throw error if wrong number
					// of args
					if (lst.size() != 3) {
						throw new Exception
						  ("Lambda expects two args.");
					}

					// return the new lambda expression
					return lambdaForm(lst, e);
				} else if
				  (car.equals
					(Symbol.getSymbol("begin"))) {

					// (begin a b) becomes (eval a)
					// then (begin b)

					o = beginForm(lst, e);
					continue;

				} else if
				  (car.equals
					(Symbol.getSymbol("define"))) {

					// throw error if wrong number
					// of args
					if (lst.size() != 3) {
						throw new Exception
						  ("Define expects two args.");
					}

					defineForm(lst, e);
					return null;
					// define returns nothing

				} else if
				  (car.equals
					(Symbol.getSymbol("quote"))) {

					// throw error if wrong number
					// of args
					if (lst.size() != 2) {
						throw new Exception
						  ("Quote expects one arg.");
					}

					// return the "quoted"
					// element without evaling it
					return lst.get(1);

				}
			}

			// We've checked for all the special
			// forms, so this list must either
			// be a function call or an error.

			// First, we need to make sure the
			// first element of the list is
			// a function. That means eval'ing it.
			// If it's a symbol corresponding
			// to a function, for example, we
			// need to eval that symbol to get
			// the function.
			root = eval(root, e);

			if (!(root instanceof Lambda)) {
				throw new Exception
				  ("Expected function, found " + root);
			}

			Lambda func = (Lambda) root;
			Environment newEnv = new
					Environment(func.getEnv());

			if (lst.size() != func.getParams().size() + 1) {
				throw new Exception
					("Wrong number of arguments: " + o);
			}

			// like above, eval all the parameters
			List<Symbol> params = func.getParams();
			for (int i = 1; i < lst.size(); i++) {
				newEnv.add(params.get(i - 1),
					eval(lst.get(i), e));
			}

			// replace the code and environment,
			// then loop to the top
			e = newEnv;
			o = func.getCode();
		}
	}
}


